home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / plane / _subdivision.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  3.3 KB  |  177 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _subdivision.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/segment.h>
  17. #include <LEDA/subdivision.h>
  18. #include <LEDA/p_dictionary.h>
  19. #include <LEDA/sortseq.h>
  20. #include <LEDA/prio.h>
  21.  
  22. static int compare(segment& s1, segment& s2);
  23.  
  24. typedef p_dictionary<segment,face> strip;
  25.  
  26. typedef p_dictionary<segment,face>* Strip_Ptr;
  27.  
  28. typedef sortseq<double,Strip_Ptr> strip_list;
  29.  
  30. typedef priority_queue<edge,point> X_structure;
  31.  
  32.  
  33.  
  34. static double x_sweep;
  35.  
  36. int compare(segment& s1,segment& s2)
  37. {
  38.   if (s1 == s2) return 0;
  39.  
  40.   double sl1 = s1.slope();
  41.   double sl2 = s2.slope();
  42.  
  43.   if (s1.start() == s2.start()) return compare(sl1,sl2);
  44.  
  45.   if (s1.end() == s2.end()) return compare(sl2,sl1);
  46.  
  47.   double y1 = sl1*x_sweep+s1.y_abs();
  48.   double y2 = sl2*x_sweep+s2.y_abs();
  49.  
  50.   return (y1 > y2) ? 1 : -1;
  51.  
  52. }
  53.  
  54. SubDivision::SubDivision(const graph& G) : planar_map(G)
  55. { 
  56.   edge e;
  57.   segment s;
  58.   point p;
  59.   strip sp;
  60.   int count = 0;
  61.  
  62.   // compute strips
  63.  
  64.   strip_list* strips = new strip_list;
  65.  
  66.   strip_ptr = (void*)strips;
  67.  
  68.   X_structure X;
  69.  
  70.   // initialize X-structure
  71.  
  72.   forall_edges(e,*this) 
  73.   { point p = position(source(e));
  74.     point q = position(target(e));
  75.  
  76.     if (p.xcoord() < q.xcoord()) 
  77.     { X.insert(e,p);
  78.       X.insert(e,q);
  79.      }
  80.    }
  81.  
  82.  
  83.  
  84.  
  85.   // sweep
  86.  
  87.   strip Y;
  88.  
  89.   x_sweep = -MAXDOUBLE;
  90.  
  91.   strips->insert(x_sweep, new strip(Y));    
  92.  
  93.   while( !X.empty() )
  94.   { point    p = X.inf(X.find_min());
  95.     list<edge> L,R;
  96.  
  97.     while ( !X.empty() )
  98.     { pq_item it = X.find_min();
  99.       point    q = X.inf(it);
  100.       edge     e = X.key(it);
  101.  
  102.       if (q != p) break;
  103.  
  104.       if (q == position(source(e)))  // left  end
  105.           L.append(e);    
  106.       else                           // right end
  107.           R.append(e);    
  108.  
  109.       X.del_item(it);
  110.      }
  111.  
  112.  
  113.     // Insert new strip into version List
  114.  
  115.     x_sweep = p.xcoord();
  116.  
  117.     edge e;
  118.     forall(e,R) Y = Y.del(segment(position(source(e)),position(target(e))));
  119.     forall(e,L) Y = Y.insert(segment(position(source(e)),
  120.                                      position(target(e))), adj_face(e));
  121.  
  122.     L.clear();
  123.     R.clear();
  124.  
  125.     strips->insert(x_sweep, new strip(Y));    
  126.  
  127.     }
  128.  
  129.    strips->insert(MAXDOUBLE, new strip(Y));    
  130.  
  131.  
  132.    // compute outer face
  133.  
  134.    seq_item sit = strips->min();
  135.    sit = strips->succ(sit);
  136.  
  137.    outer_face = Y.inf(strips->inf(sit)->min());
  138.  
  139. }
  140.  
  141.  
  142.  
  143. face SubDivision::locate_point(point p) const
  144. {
  145.   strip_list* strips = (strip_list*)strip_ptr;
  146.  
  147.   seq_item sit = strips->locate(p.xcoord()); 
  148.   Strip_Ptr Y = strips->inf(strips->pred(sit));
  149.   x_sweep = p.xcoord();
  150.   p_dic_item it = Y->locate(segment(p,0,1));
  151.   return (it == nil) ? outer_face : Y->inf(it);
  152.  }
  153.  
  154.  
  155. void SubDivision::print_stripes() const
  156. { seq_item it1;
  157.   p_dic_item it2;
  158.   strip_list* strips = (strip_list*)strip_ptr;
  159.  
  160.   forall_items(it1,*strips)
  161.   { Strip_Ptr sp = strips->inf(it1);
  162.     forall_items(it2,*sp) 
  163.       cout << sp->key(it2) << " f = " << int(sp->inf(it2)) << "\n";
  164.     newline;
  165.   }
  166.   newline;
  167.  }
  168.  
  169. SubDivision::~SubDivision() 
  170. { strip_list* strips = (strip_list*)strip_ptr;
  171.   seq_item it;
  172.   forall_items(it,*strips) delete strips->inf(it);
  173.   delete strips; 
  174. }
  175.  
  176.  
  177.